package double_linked_list;

public class Test {
    public static void main(String[] args) {
        doubleLinkedList list = new doubleLinkedList();
        list.addFirst(2);
        list.addLast(2);
        list.addLast(3);
        list.addLast(2);
        list.addIndex(1, 4);
        list.addLast(2);
        System.out.println(list);
        list.deleteValueAll(2);
//        list.deleteValueOnce(5);
//        list.deleteIndex(3);
//        System.out.println(list.queryValue(1));
//        list.reverseValue(1, 6);
        System.out.println(list);
    }
}

/**
 * 用来创建以及管理双链表
 */
class doubleLinkedList {
    Node headNode;
    int size;
    Node tailNode;

    public doubleLinkedList() {}

    public doubleLinkedList(Node headNode, int size, Node tailNode) {
        this.headNode = headNode;
        this.size = size;
        this.tailNode = tailNode;
    }

    /**
     * 头插
     * @param value
     */
    public void addFirst(int value) {
        Node node = new Node(value);
        node.next = headNode;
        headNode = node;
        if (size == 0) {
            tailNode = node;
        }
        size ++;
    }

    /**
     * 尾插
     * @param value
     */
    public void addLast(int value) {
        Node node = new Node(tailNode, value);
        if (size == 0) {
            headNode = node;
        } else {
            tailNode.next = node;
        }
        tailNode = node;
        size ++;
    }

    /**
     * 在任意位置插入
     * @param index
     * @param value
     */
    public void addIndex(int index, int value) {
        String flag = "add";
        if (indexIsIllegal(index, flag)) {
            if (index == 0) {
                addFirst(value);
            } else if (index == size) {
                addLast(value);
            } else {
                Node node = new Node(value);
                Node tmpNode = headNode;
                for (int i = 0; i < index - 1; i++) {
                    tmpNode = tmpNode.next;
                }
                node.next = tmpNode.next;
                tmpNode.next.prev = node;
                tmpNode.next = node;
                node.prev = tmpNode;
                size ++;
            }
        }
    }

    /**
     * 查询任意位置的值
     * @param index
     * @return
     */
    public int queryValue(int index) {
        String flag = "query";
        if (indexIsIllegal(index, flag)) {
            Node tempNode = headNode;
            for (int i = 0; i < index; i++) {
                tempNode = tempNode.next;
            }
            return tempNode.value;
        }
        return -1;
    }

    /**
     * 修改某处的值
     * @param index
     * @param newValue
     * @return
     */
    public int reverseValue(int index, int newValue) {
        String flag = "reverse";
        if (indexIsIllegal(index, flag)) {
            Node tempNode = headNode;
            for (int i = 0; i < index; i++) {
                tempNode = tempNode.next;
            }
            int oldValue = tempNode.value;;
            tempNode.value = newValue;
            return oldValue;
        }
        return -1;
    }

    private void unlink(Node node) {
        //分治思想
        Node prev = node.prev;
        Node next = node.next;
        // 先处理前驱节点
        if (prev == null) {
            headNode = next;
        } else {
            prev.next = next;
            node.prev = null;
        }
        // 处理后继节点
        if (next == null) {
            tailNode = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }
        size --;
    }

    private Node findNode(int index) {
        Node ret = null;
        // 此方法是用在其他方法中的所以该index合法性已经判断过，肯定合法
        if (index < (size >> 1)) {
            ret = headNode;
            for (int i = 0; i < index; i++) {
                ret = ret.next;
            }
        } else {
            ret = tailNode;
            for (int i = size - 1; i > index; i--) {
                ret = ret.prev;
            }
        }
        return ret;
    }

    /**
     * 删除任意位置处节点
     * @param index
     * @return
     */
    public int deleteIndex(int index) {
        String flag = "delete";
        if (indexIsIllegal(index, flag)) {
            Node node = findNode(index);
            unlink(node);
            return node.value;
//            Node tempNode = headNode;
//            if (index < (size - 1) /2) {
//                if (index == 0) {
//                    int value = headNode.value;
//                    headNode = headNode.next;
//                    headNode.prev = null;
//                    size --;
//                    return value;
//                } else {
//                    for (int i = 0; i < index; i++) {
//                        tempNode = tempNode.next;
//                    }
//                }
//            } else {
//                if (index == size - 1) {
//                    int value = tailNode.value;
//                    tailNode = tailNode.prev;
//                    tailNode.next = null;
//                    size --;
//                    return value;
//                } else {
//                    tempNode = tailNode;
//                    for (int i = size - 1; i > index; i--) {
//                        tempNode = tempNode.prev;
//                    }
//                }
//            }
//            int value = tempNode.value;
//            tempNode.next.prev = tempNode.prev;
//            tempNode.prev.next = tempNode.next;
//            tempNode.prev = tempNode.next = null;
//            size --;
//            return value;
        }
        return -1;
    }

    /**
     * 删除第一次出现值为value的节点
     * @param value
     * @return
     */
    public void deleteValueOnce(int value) {
        Node tempNode = headNode;
        for (int i = 0; i < size; i++) {
            if (tempNode.value == value) {
                deleteIndex(i);
                return;
            }
            tempNode = tempNode.next;
        }
    }

    /**
     * 删除所有值为value的节点
     * @param value
     */
    public void deleteValueAll(int value) {
        Node tempNode =headNode;
        while (tempNode != null) {
            Node nextTemp = tempNode.next;
            if (tempNode.value == value) {
                deleteValueOnce(value);
            }
            tempNode = nextTemp;
        }
    }

    /**
     * 判断index是否合法
     * @param index
     * @param flag
     * @return
     */
    private boolean indexIsIllegal(int index, String flag) {
        if (flag.equals("add") || flag.equals("query") || flag.equals("reverse")) {
            if (index < 0 || index > size) {
                System.out.println("index is illegal!");
                return false;
            }
        } else if (flag.equals("delete")) {
            if (index < 0 || index >= size) {
                System.out.println("index is illegal!");
                return false;
            }
        }
        return true;
    }

    public String toString() {
        Node tmpNode = headNode;
        String str = "";
        while (tmpNode != null) {
            str += tmpNode.value + "->";
            tmpNode = tmpNode.next;
        }
        str += "NULL";
        return str;
    }
}

/**
 * 双链表中的节点
 */
class Node {
    Node prev;
    int value;
    Node next;

    public Node(){}

    public Node(Node prev, int value) {
        this.prev = prev;
        this.value = value;
    }

    public Node(int value) {
        this.value = value;
    }
}